二叉平衡搜索树

• 每个节点的左子树与右子树的高度不超过 1

function Node (value) {
    this.value = value;
    this.left = null;
    this.right = null;
}

const a = new Node('a');
const b = new Node('b');
const c = new Node('c');
const d = new Node('d');
const e = new Node('e');
const f = new Node('f');
const g = new Node('g');

a.left = b;
b.left = d;
b.right = e;
c.left = f;
c.right = g;

是否为平衡树

// 获取二叉树的深度
function getDeep (root) {
    if (root == null || root == undefined) return 0;
    let leftDeep = getDeep(root.left);
    let rightDeep = getDeep(root.right);
    return Math.max(leftDeep, rightDeep) + 1;
}

// 二叉树是否平衡
function isBalance (root) {
    if (root == null) return true;
    let leftDeep = getDeep(root.left);
    let rightDeep = getDeep(root.right);
    if (Math.abs(leftDeep - rightDeep) > 1) {  // 不平衡
        return false;
    } else {
        return isBalance(root.left) && isBalance(root.right);
    }
}

console.log(getDeep(a));  //--> 3
console.log(isBalance(a));  //--> false

单璇

• 左单璇：右子树比左子树深度深，需进行左单璇
• 右单璇：左子树比右子树深度深，需进行右单璇
• 怎样做单璇：
  • 不平衡的节点为旋转节点

// 左旋
function leftRotate (root) {
    let newRoot = root.right;  // 新的根
    let changeTree = root.right.left;
    root.right = changeTree;
    newRoot.left = root;
    return newRoot;
}
// 右旋
function rightRotate (root) {
    let newRoot = root.left;
    let changeTree = root.left.right;
    root.left = changeTree;
    root.right = root;
    return newRoot;
}

function change (root) {
    if (isBalance(root)) return root;
    if (root.left != null) root.left = change(root.left);
    if (root.right != null) root.right = change(root.right);
    let leftDeep = getDeep(root.left);
    let rightDeep = getDeep(root.right);
    if (Math.abs(leftDeep - rightDeep) < 2) {  // 平衡
        return root;
    } else if (leftDeep > rightDeep) {  // 左子树深，进行右旋
        return rightRotate(root);
    } else {  // 右子树深，进行左旋
        return leftRotate(root);
    }
    return root;
}

const newRoot = change(a);  // 单璇后看谁是根节点，再进行 isBalance 判断
console.log(isBalance(newRoot));  //--> true

双璇

为解决左子树或右子树单一边有子节点的问题

• 左右双璇与右左双璇
  • a.left = b, b.left = c, c.left = d, d.left = e, e.left = f; ```js function change (root) { if (isBalance(root)) return root; if (root.left != null) root.left = change(root.left); if (root.right != null) root.right = change(root.right); let leftDeep = getDeep(root.left); let rightDeep = getDeep(root.right); if (Math.abs(leftDeep - rightDeep) < 2) { // 平衡 return root; } else if (leftDeep > rightDeep) { // 左子树深，进行右旋 let changeTreeDeep = getDeep(root.left.right); let noChangeTreeDeep = getDeep(root.left.left); if (changeTreeDeep > noChangeTreeDeep) { root.left = leftRotate(root.left); } return rightRotate(root); } else { // 右子树深，进行左旋 let changeTreeDeep = getDeep(root.right.left); let noChangeTreeDeep = getDeep(root.right.right); if (changeTreeDeep > noChangeTreeDeep) { root.right = rightRotate(root.right); } return leftRotate(root); } return root; }

const newRoot = change(a); console.log(isBalance(newRoot)); //--> true

- 左左双璇与右右双璇

```js
function change (root) {
    if (isBalance(root)) return root;
    if (root.left != null) root.left = change(root.left);
    if (root.right != null) root.right = change(root.right);
    let leftDeep = getDeep(root.left);
    let rightDeep = getDeep(root.right);
    if (Math.abs(leftDeep - rightDeep) < 2) {  // 平衡
        return root;
    } else if (leftDeep > rightDeep) {  // 左子树深，进行右旋
        let changeTreeDeep = getDeep(root.left.right);
        let noChangeTreeDeep = getDeep(root.left.left);
        if (changeTreeDeep > noChangeTreeDeep) {
            root.left = leftRotate(root.left);
        }
        let newRoot = rightRotate(root);
        newRoot.right = change(newRoot);
        newRoot = change(newRoot);
        return newRoot;
    } else {  // 右子树深，进行左旋
        let changeTreeDeep = getDeep(root.right.left);
        let noChangeTreeDeep = getDeep(root.right.right);
        if (changeTreeDeep > noChangeTreeDeep) {
            root.right = rightRotate(root.right);
        }
        let newRoot = leftRotate(root);
        newRoot.left = change(newRoot);
        newRoot = change(newRoot);
        return newRoot;
    }
    return root;
}